package dem1;

import javax.xml.soap.Node;
import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 33013
 * Date: 2023-04-11
 * Time: 22:04
 */

 class LinkedList {
    //头插法

    private Node head;
    private Node last;
    private int size;

    class Node{
        private int val;
        private Node prev;
        private Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node() {
        }

    }

    public LinkedList() {
    }

    public void addFirst(int data){
        size++;
        Node node = new Node(data);
        if (head == null){
            head = node;
            last = node;
            return;
        }
        node.next = head;
        head.prev = node;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        size++;
        Node node = new Node(data);
        if (head == null){
            head = node;
            last = node;
            return;
        }
        last.next = node;
        node.prev = last;
        last = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if (index == 0){
            addFirst(data);
        }else if (index == size){
            addLast(data);
        }else {
            Node cur = head;
            while (index != 0){
                cur = cur.next;
                index--;
            }
            Node node = new Node(data);
            node.prev = cur.prev;
            node.next = cur;
            cur.prev.next = node;
        }
        size++;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        Node cur = head;
        while (cur != null){
            if (cur.val == key){
                if (cur == head){
                    head = head.next;
                    if (size == 1){
                        return;
                    }
                    head.prev = null;
                }else if (cur == last){
                    last = last.prev;
                    last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                size--;
                return;
            }else {
                cur = cur.next;
            }
        }
        return;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        Node cur = head;
        while (cur != null){
            if (cur.val == key){
                if (cur == head){
                    head = head.next;
                    if (size == 1){
                        return;
                    }
                    cur = head;
                    head.prev = null;
                }else if (cur == last){
                    last = last.prev;
                    last.next = null;
                    break;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    cur = cur.next;
                }
                size--;
            }else {
                cur = cur.next;
            }
        }
        return;
    }
    //得到单链表的长度
    public int size(){
        return size;
    }
    public void display(){
        Node cur = head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
        size = 0;
        while (head != null){
            head.prev = null;
            head = head.next;
        }
        head = null;
        last = null;
    }
}

public class Test1 {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        //list.clear();
        list.addLast(1);
        //list.clear();
        list.addLast(2);
        list.addLast(3);
        //list.addFirst(0);
        list.addLast(1);
        list.addLast(3);
        list.addLast(5);
        list.addLast(1);
        list.removeAllKey(1);
        //list.display();
//      list.addIndex(1,5);
//      list.addIndex(5,6);
//      list.addIndex(0,-1);
        //list.remove(2);
        list.display();

    }
}
